package com.LeeG.work.search;

import java.util.Scanner;

/**
 * @author LeeG
 * @Description: 二分搜索
 * @date 2021/1/19 13:57
 */
public class BinarySearch {

    private static final int[] array = {2, 4, 8, 8, 8, 9, 12};

    public static void main(String[] args) {
        System.out.println(searchIndexOf(1));
    }

    /**
     * 查找target在有序数组array中的下标
     * @param target
     * @return
     */
    public static int searchTarget(int target) {
        int begin = 0;
        int end = array.length;
        while (begin < end) {
            int mid = (begin + end) >> 1;
            if (array[mid] < target) {
                begin = mid + 1;
            } else if (array[mid] > target) {
                end = mid;
            } else {
                return mid;
            }
        }
        return -1;
    }

    /**
     * 查找value在有序数组array中的插入位置
     * @param value
     * @return
     */
    public static int searchIndexOf(int value) {
        int begin = 0;
        int end = array.length;
        while (begin < end) {
            int mid = (begin + end) >> 1;
            if (array[mid] <= value) {
                begin = mid + 1;
            } else if (array[mid] > value) {
                end = mid;
            }
        }
        return begin;
    }
}
